In order to effectively encode motion picture data via high-compression coding techniques, four kinds of redundancies must be removed from the data. First, redundancy in signal constituents must be removed. Second, statistical redundancy, which results from the statistical probability of data generation, must be removed. Third, time redundancy between frames of the motion picture data must be removed. Fourth, spatial redundancy existing within the frames of the motion picture data must be removed.
The redundancy existing in the signal constituents can be reduced by using a signal having a brightness to chromaticity ratio of 2:1. Also, the statistical redundancy can be reduced via a variable length coding technique which uses the probability of data generation during the coding process to reduce the average number of bits of the data. In addition, the spatial redundancy can be reduced by performing discrete cosine transformation (“DCT”) techniques. Finally, the time redundancy, which is substantially contained in the moving pictures, can be reduced by motion estimation (“ME”) and motion compensation (“MC”).
In one motion estimation method, a full search method (“FSM”) is used as a block-matching algorithm to reduce the time redundancy. However, when the method is used as a block-matching algorithm, the complexity of an encoder for encoding the motion picture data depends on a motion estimation algorithm. Thus, although this method is capable of highly compressing the motion picture data during the encoding process, the overall performance of the encoder implementing the FSM is low because the block-matching algorithm is extremely complex.
In another motion estimation method, the complexity of the block-matching algorithm is decreased by performing a three-step search (“3SS”) or a four-step search (“4SS”). Such types of methods are well-known and will not be described in detailed for the sake of brevity. In such methods, the algorithm analyzes a current block and searches for a block which is the most similar to the current block by comparing the current block with all blocks within a fixed search region. The 3SS method and the 4SS method can estimate motion with a relatively low degree of complexity. However, in order to increase the speed at which motion can be estimated, a motion estimation method that is capable of performing a block matching routine even more quickly is needed. Accordingly, a block matching algorithm that is even less complex than the 3SS method and the 4SS method is required.